package ljl.alg.wangzheng_camp.round1.stack_and_queue;

import java.util.LinkedList;

/**
 * 给定一个整数数组 temperatures，表示每天的温度，
 * 返回一个数组 answer，
 * 其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。
 * 如果气温在这之后都不会升高，请在该位置用 0 来代替。
 *
 * 输入: temperatures = [73,74,75,71,69,72,76,73]
 * 输出:[1,1,4,2,1,1,0,0]
 */
public class _739_each_day_degree {
    
    public int[] dailyTemperatures22(int[] temperatures) {
        int n = temperatures.length;
        LinkedList<Integer> stack = new LinkedList<>();
        int[] res = new int[n];
    
        for (int i = 0; i < n; i++) {
            int t = temperatures[i];
            while (!stack.isEmpty() && t > temperatures[stack.peek()]) {
                int p = stack.pop();
                res[p] = i - p;
            
            }
            stack.push(i);
        }
    
        return res;
    }
    
    /*
    * 很简单的一个单调栈应用，特别简单
    * 如果不会那就是。。不会
    * */
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            int t = temperatures[i];
            while (!stack.isEmpty() && temperatures[stack.peek()] < t) {
                int j = stack.pop();
                res[j] = i - j;
            }
            stack.push(i);
        }
        return res;
    }
    
}
